1. Field of the Invention
The present invention concerns encoding/decoding using convolutional codes.
2. Description of the Prior Art
Convolutional codes (also called convolutive codes or recurrent codes) are essentially codes generated from a sequence of digital data applied in the form of a stream of consecutive bits to the input of an encoder, the data being convoluted by means of generator polynomials and operations being always conducted modulo 2. A simple way to implement convolution uses an encoder comprising a register in the form of a series of .nu. D flip-flops whose outputs are combined by gates in a particular configuration specific to the required encoding to produce at the output a stream of encoded binary data. The flip-flops are configured as a shift register with the result that the encoding of a current information bit depends not only of the value of the current input bit but also on the value of the .nu. previous bits.
An encoder of this kind can be regarded as an automatic device with a finite number of states. These states and the transitions between them can be represented in the form of a trellis. A path within this trellis represents an encoded sequence, analogous to a code word.
These various topics are discussed in the French translation (by G. Battail) under the title Principes des communication numeriques of the book by A. J. Viterbi and J. K. Omura published by Dunod in 1982, in Theory and Practice of Error Control Codes R. E. Blahut, addison-Westley, 1984 and in Elements de communications numeriques, J. C. Bic, B. Duponteil and J. C. Imbeaux, Dunod, 1986, which provides a comprehensive and in-depth treatment of the general principles of convolutional codes.
Encoding a digital bit stream therefore consists in crossing the trellis along one possible path, each new bit of the stream of information determining a branch in the path and causing the simultaneous transmission of "parity" bits relating to the path followed.
The parity bits are then transmitted to a receiver and an associated decoder.
The parity bits received include a number of errors due to transmission defects (noise, jamming, etc).
Decoding at the receiving end therefore involves, starting from the stream of received parity bits affected by noise, reconstituting the trellis path determined by the encoder at the transmitting end and so recovering the sequence of information bits that caused this path to be selected in the encoding process.
The best method of decoding a digital bit stream affected by noise is the "Viterbi algorithm", which is a maximum probability type decoding algorithm.
In outline, a first stage of this algorithm compares all the parity bit streams for all the possible trellis paths with the streams actually received and calculates for each one the distance between two received parity bits and the corresponding bits of each branch. This distance, integrated over the length of the branches of the path, defines a "branch metric".
The next stage of the Viterbi algorithm determines a "path metric" which is the sum of the branch metrics for a given path. It then selects from all the paths analyzed the one with the lowest metric.
For each pair of parity bits received the number of possible paths will be doubled at least (it will be multipled by n if the code yield is 1/n but n-1 paths will be eliminated). There remains at each stage a constant number of paths to be extended; these are the "survivor paths".
Each extension of a path entails choosing one of n possible branches, and this choice is characterized by a bit which represents the information bit that caused the encoder to apply the transition in question--in other words, this is the original information bit that is to be restored.
The final stage of the Viterbi algorithm stores the survivor paths obtained in this way and scans them in the reverse direction, from the most recent towards the least recent, and retains only one, representing the required information (to be more precise, an optimal--in the sense of maximum probability--estimate of the original sequence transmitted).
This stage, which is the stage implemented by a circuit in accordance with the present invention, is usually referred to in this art as the "traceback stage".
Various hardware and software implementations have been proposed for this function.
An object of the present invention is to propose a specific circuit structure enabling this stage of the algorithm to be executed at high speed in hardware, to allow real time processing of a high information rate incoming data stream.
The traceback principle is known in itself and entails storing in memory previously determined survivor paths, although the paths are in fact retained only for the number of branches for which they are different, this number being referred to as the "truncation length" L.
As the survivor paths in fact differ only in their L most recent branches, by tracing back beyond a certain number of branches they all converge towards a single path in respect of which there is no ambiguity.
The survivor paths are stored in a memory three-deep containing 3 L words each of N bits (N=2.sup..nu. being the number of states of the trellis and L being the truncation length for the code in question).
One of these three blocks is written and the other two are read; when the write block is full it is switched to read mode and the earlier of the read mode blocks to be filled is switched to write mode; this process is repeated.
Each time that a word is written into the memory, two words are simultaneously read (so that reading is twice as fast as writing), with the result that the path reading system traces the paths back over two truncation lengths.
After L nodes, the path being traced back will have joined the point of convergence of all the paths so that the path traced back on the second truncation length will definitely be the required single path, for which an unambiguous decision can be taken as to the reconstruction of the bits transmitted.
FIG. 1 is a diagram showing the hardware implementation of this stage as used until now.
The memory 10 contains the three blocks each of L words each of N bits. It receives on its input side the data D, the read addresses A.sub.1 and the write addresses A.sub.e.
At its output the memory 10 delivers words D formed of 2.sup..nu. bits that can be written: EQU D=B.sub.0, B.sub.1 . . . B.sub.i . . . B.sub.2.sup..nu. -1.
The bit B.sub.i of the data word D represents the decision regarding the node i. If i is written in binary, its value will be represented by a word of .nu. bits, for example: EQU i={A.sub..nu.-1 A.sub..nu.-2 . . . A.sub.0 }.
The following example assumes .nu.=6 so that N=2.sup.6 =64, which value is routinely used but is in no way limiting on the invention.
The words D are thus formed of the bits B.sub.i : EQU D=B.sub.0, B.sub.1 l l l B.sub.i . . . B.sub.63.
The subscript i can then be represented by a six-bit word in the form: EQU i={A.sub.5, A.sub.4 . . . A.sub.0 }.
Because the ith bit B.sub.i represents the information bit output from the encoder to reach the node i of the trellis from the node j of the previous stage, it is easy to determine the antecedent node j: its number is obtained by halving the number of the start node and adding to it the bit B.sub.i multiplied by 2.sup..nu.-1 : EQU j=i/2+B.sub.i .multidot.2.sup..nu.-1
As N=2.sup..nu., the number i is encoded on .nu. bits that can be stored in a shift register. The operation just described can therefore be implemented simply by a rightward shift of the register and entering the bit B.sub.i into the register input (the leftmost flip-flop, that containing the most significant bit).
In the other implementation used until now (FIG. 1), the bits B.sub.0, B.sub.1, etc were applied to the 2.sup..nu. inputs of a 2-in-1 multiplexer (in this example, the 64-in-1 multiplexer 11 shown in the figure) outputting a bit S(t) which will be the bit B.sub.i selected at the read address applied to the memory 10 at the time t by the multiplexer commanded by the word {S(t-1), . . . S(t-.nu.)} (which is the six-bit word {S(t-1), S(t-6)} in this example).
This circuit uses a shift register 12, referred to hereinafter as the "traceback register", comprising .nu. flip-flops 13 in cascade (.nu.=6 in this example). Each flip-flop outputs one of the bits of the multiplexer control word and the last flip-flop outputs the required information bit (with a delay of stages which is inherent to the algorithm).
Despite its apparent simplicity, this hardware implementation has the serious drawback that when .nu. takes relatively high values (for example .nu.=6, as in this example) the multiplexing operation is relatively long and limits the maximum speed at which the system can operate.
As the system is looped, it is highly sensitive to internal time-delays (caused by the hardware, essentially the multiplexer and therefore dependent on the technology employed), and the input data information rate will necessarily be limited to a value compatible with the cumulative result of all these internal delays.
An object of the present invention is to propose a new hardware architecture for implementing the traceback algorithm which circumvents this multiplexing delay to enable an increase in the speed of execution of the traceback function.
A circuit in accordance with the invention is a circuit of the aforementioned type, that is to say a convolutional code decoding circuit for executing the stage of a Viterbi algorithm which involves reverse scanning of a plurality of paths of a trellis representing a diagram of possible transitions resulting from encoding by an encoder comprising .nu. flip-flops, each node of the trellis being represented by a word of N=2.sup..nu. bits, said circuit selecting from a plurality of possible survivor paths that having the lowest metric, so as to reconstitute the trellis path determined during encoding and to recover the sequence of information bits causing said path to be adopted.
Essentially, the invention proposes to subdivide the multiplexing operation into a plurality of simpler multiplexing operations implemented between the flip-flops of the shift register, in other words to interleave the multiplexing circuits and the traceback register stages, rather than having the register as a unit connected to the output of a multiplexer, as in the prior art.
The traceback register will therefore have a distributed structure, with at least one multiplexing circuit interleaved between two consecutive register stages.
It will be realised that an architecture of this kind makes it possible to use much simpler and therefore faster multiplexers.